package org.example.code.test2024.nine_mouth;

import org.example.code.test2024.eight_mouth.TreeNode;

import java.util.*;

public class test0903 {
    public void flatten(TreeNode root) {
        while (root != null) {
            if (root.left == null) {
                root = root.right;
            } else {
                TreeNode pre = root.left;
                while (pre.right != null) {
                    pre = pre.right;
                }
                pre.right = root.right;
                root.right = root.left;
                root.left = null;
                root = root.right;
            }
        }
    }

    //前序： 根左右
    //中序: 左根右
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder == null || inorder == null || preorder.length != inorder.length)
            return null;
        return build(preorder,0,preorder.length-1,inorder,0,inorder.length-1);
    }

    private TreeNode build(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd) {
        if(preStart > preEnd || inStart > inEnd)
            return null;
        int rootVal = preorder[preStart];
        int index = 0;
        for(int i = inStart; i <= inEnd; i++) {
            if(inorder[i] == rootVal) {
                index = i;
                break;
            }
        }
        TreeNode root = new TreeNode(rootVal);
        root.left = build(preorder, preStart+1, preStart+index-inStart, inorder, inStart, index-1);
        root.right = build(preorder, preStart+index-inStart+1, preEnd, inorder, index+1, inEnd);
        return root;
    }

    public int pathSum(TreeNode root, long targetSum) {
        if(root == null)
            return 0;
        int count = rootSum(root,targetSum);
        count = count + pathSum(root.left,targetSum);
        count = count + pathSum(root.right,targetSum);
        return count;
    }

    private int rootSum(TreeNode root, long targetSum) {
        int count = 0;
        if(root == null)
            return 0;
        if(root.val == targetSum){
            count++;
        }
        count = count + rootSum(root.left,targetSum-root.val);
        count = count + rootSum(root.right,targetSum-root.val);
        return count;
    }


    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null || root == p || root == q)
            return root;
        TreeNode left = lowestCommonAncestor(root.left,p,q);
        TreeNode right = lowestCommonAncestor(root.right,p,q);
        if(left != null && right != null)
            return root;
        return left != null ? left : right;
    }

    int max = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        maxPathSumHelper(root);
        return max;
    }

    private int maxPathSumHelper(TreeNode root) {
        if(root == null)
            return 0;
        int left = Math.max(maxPathSumHelper(root.left),0);
        int right = Math.max(maxPathSumHelper(root.right),0);
        int val = root.val + left + right;
        max = Math.max(max,val);
        return Math.max(left,right) + root.val;
    }

    public int numIslands(char[][] grid) {
        if(grid == null || grid.length == 0 || grid[0].length == 0)
            return 0;
        int count = 0;
        for(int i = 0; i < grid.length; i++) {
            for(int j = 0; j < grid[0].length; j++) {
                if(grid[i][j] == '1') {
                    dfs(grid,i,j);
                    count++;
                }
            }
        }
        return count;
    }
    int []a = {0,0,1,-1};
    int []b = {1,0,-1,0};
    private void dfs(char[][] grid, int x, int y) {
        if(grid[x][y]=='0')
            return ;
        grid[x][y] = '0';
        for(int i = 0; i < 4; i++) {
            int xx = x+a[i];
            int yy = y+b[i];
            if(xx >= 0 && xx < grid.length && yy >= 0 && yy < grid[0].length) {
                dfs(grid, xx, yy);
            }
        }
    }

    public int orangesRotting(int[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }
        int nr = grid.length;
        int nc = grid[0].length;
        int minutes = 0;
        Queue<int[]> q = new LinkedList<>();
        for (int r = 0; r < nr; ++r) {
            for (int c = 0; c < nc; ++c) {
                if (grid[r][c] == 2) {
                    q.offer(new int[]{r, c});
                }
            }
        }
        while (!q.isEmpty()&&!check(grid)) {
            int size = q.size();
            for (int i = 0; i < size; ++i) {
                int[] curr = q.poll();
                int r = curr[0];
                int c = curr[1];
                if (r > 0 && grid[r - 1][c] == 1) {
                    grid[r - 1][c] = 2;
                    q.offer(new int[]{r - 1, c});
                }
                if (r < nr - 1 && grid[r + 1][c] == 1) {
                    grid[r + 1][c] = 2;
                    q.offer(new int[]{r + 1, c});
                }
                if (c > 0 && grid[r][c - 1] == 1) {
                    grid[r][c - 1] = 2;
                    q.offer(new int[]{r, c - 1});
                }
                if (c < nc - 1 && grid[r][c + 1] == 1) {
                    grid[r][c + 1] = 2;
                    q.offer(new int[]{r, c + 1});
                }
            }
            ++minutes;
        }

        return check(grid)? minutes  : -1;
    }

    private boolean check(int[][] grid){
        for (int r = 0; r < grid.length; ++r) {
            for(int c = 0; c < grid[0].length; ++c) {
                if(grid[r][c] == 1)
                    return false;
            }
        }
        return true;
    }

    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<List<Integer>> adjList = new ArrayList<>();
        int[] inDegree = new int[numCourses];
        for (int i = 0; i < numCourses; i++) {
            adjList.add(new ArrayList<>());
        }

        // 构建图和入度数组
        for (int[] prerequisite : prerequisites) {
            int course = prerequisite[0];
            int preCourse = prerequisite[1];
            adjList.get(preCourse).add(course);
            inDegree[course]++;
        }

        // 找到所有入度为0的节点
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (inDegree[i] == 0) {
                queue.offer(i);
            }
        }

        int[] order = new int[numCourses];
        int index = 0;

        // BFS遍历
        while (!queue.isEmpty()) {
            int current = queue.poll();
            order[index++] = current;

            for (int neighbor : adjList.get(current)) {
                inDegree[neighbor]--;
                if (inDegree[neighbor] == 0) {
                    queue.offer(neighbor);
                }
            }
        }

        // 如果结果中的课程数量不等于numCourses，说明存在循环依赖
        if (index != numCourses) {
            return false;
        }

        return true;
    }


}